/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package shaman.storage.impl.util;

import java.util.Iterator;

/**
 *
 * @author dmitriy
 */
public class OffsetMap<V> implements Iterable<V> {

    private class OffsetMapIterator implements Iterator<V> {

        int index=0;

        public OffsetMapIterator() {
        }

        public boolean hasNext() {
            return (index<count);
        }

        public V next() {
            if (index<count)
                return (V) objects[index++];
            else
                return null;
        }

        public void remove() {
            if (index>0){

                doRemove(index-1);
                index--;
            }
        }

    }

    private long[] offsets;
    private Object[] objects;
    private int count;
    
    public static final int MIN_CAP=16;

    public OffsetMap() {
        offsets=new long[MIN_CAP];
        objects=new Object[MIN_CAP];
        count=0;
    }

    public void add(long offset, V obj)
    {
        if (count==offsets.length)
            resize(offsets.length<<1);
        int idx=getIndex(offset);
        int i;
        for (i=count-1; i>idx; i--)
        {
            offsets[i+1]=offsets[i];
            objects[i+1]=objects[i];
        }
        offsets[idx+1]=offset;
        objects[idx+1]=obj;
        count++;
    }

    public V get(long offset)
    {
        int idx=getIndex(offset);
        return (V) objects[idx];
    }

    public void remove(long offset)
    {
        doRemove(offset);
    }

    protected void doRemove(long offset) {
        int idx=getIndex(offset);
        if (idx<0 || offsets[idx]!=idx)
            throw new IllegalArgumentException("Deleting nonexistent element");
        int i;
        for (i=idx; i<count-1; i++)
        {
            offsets[i]=offsets[i+1];
            objects[i]=objects[i+1];
        }
        count--;
        if (count>=MIN_CAP && count<=offsets.length>>2)
            resize(offsets.length>>1);
    }

    public int getIndex(long offset)
    {
        int left=0;
        int right=count-1;
        while (right-left>=2)
        {
            int mid=(left+right)/2;
            if (offsets[mid]<=offset)
                left=mid;
            if (offsets[mid]>=offset)
                right=mid;
        }
        if (left>=right)
            return right;
        else if (offsets[left]<=offset && offset<offsets[right])
            return left;
        else if (offset<offsets[left] && left==0)
            return -1;
        else
            return right;
    }

    public V getItemAt(int index) {
        if (index<count)
            return (V) objects[index];
        else
            throw new IndexOutOfBoundsException("Illegal index: "+index);
    }

    protected void resize(int newlength)
    {
        long[] newOffsets=new long[newlength];
        Object[] newObjects=new Object[newlength];
        System.arraycopy(offsets, 0, newOffsets, 0, count);
        System.arraycopy(objects, 0, newObjects, 0, count);
        offsets=newOffsets;
        objects=newObjects;
    }

    public Iterator<V> iterator() {
        return new OffsetMapIterator();
    }

}
